Two Pointer

Window

Squeeze

Three Sum

Fast and Slow

LC109：找linked list中间值
判断linked list成环

Two Way Scan

DFS / backtracing

Move Inside an Array Or maybe can solve by DP

LC489. Robot Room Cleaner
iterator的DFS，需要一个stack和一个visited

stack s;

while(true) {

visit;

bool moved = false;

for(all children c) {

if(c not visited) {

s.push(current_state);

state = new_state;

move = true;

break;

}

if(moved) {

continue;

}

if(s.empty()) {

break;

}

state = s.top();

s.pop();

}

Recursion

递归的思想：要么简化成若干个子问题，要么直接解决问题

LC1096. Brace Expansion II

Tree Traversal

recursion验证，对于可以递归定义的题，可以recursion
LC333. Largest BST Subtree

另外比如检查树是不是对称的，需要两个pointer来recursion

Permutation / Combination

LC47. Permutations II

BFS

Topological Sort

遇到需要先后次序的题，考虑建图然后Topological sort

LC444. Sequence Reconstruction

Matrix Sorting

Input:
1 5 6
4 3 2
8 7 9
Output:
1 3 4
3 2 1
5 4 6

Stack

Heap

LC23 Merge k Sorted Lists

DP

DP的理解
two attribute for DP problem

optimal substructure: the optimal solution can be obtained by combination of optimal solutions to sub-problems
如果只有这一个条件，就是divide and conquer/recursive
overlapping sub-problems
the sub-problem will be solved more than once

两种方法

top-down approach: memorize solution to each sub-problem and solve the problem recursively
bottom-up approach: solve the small sub-problems first

思考DP方程的时候有两种方法；

Divide and Conquer：一般是从中间划分成两部分，遍历所有划分方案
DFS + memorization：一般是逐步外推

LC403. Frog Jump
DP可以看作是DFS的改进，思考的时候可以先从DFS开始，然后找overlap sub-problem
对于搜索空间很大时，DP不一定是vector，也可以是map
尤其是题目对搜索空间有限制的时候，更可能是DP

Move Inside an Array

经典DP寻路，如果是DP需要上面和左边的点的信息，只需要先行后列遍历即可

LC410. Split Array Largest Sum
DP方程不一定都从其他方程推出来，也可以结合输入

LC552. Student Attendance Record II
类似一个数学问题，考虑能不能递推（利用上一次的信息）

Tricky DP

LC239. Sliding Window Maximum

max_left(i) and max_right(i)

LC239. Sliding Window Maximum

LC rain water

Hash Table / Prefix Tree

prefix tree和hash table的区别就是prefix tree可以支持start_with查询
一样的地方在于都可以insert/find/remove

Two Sum
Word Search II

Linked List / Deque

报数问题
Sliding Window Maximum：Deque

实现一个带tag的queue，push的时候有tag，pop的时候可以指定tag，也可以不指定

Sort

Merge Interval

Random

Greedy

LC240. Search a 2D Matrix II
直接可以排除一行或者一列

Greedy 总结

LC53 Maximum Subarray

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

求下一个排列
找按数字顺序递增，且比当前数字小，且尽量大的数字

12332 -> 12299

LC402. Remove K Digits

LC680. Valid Palindrome II
可以直接从外向内检查

LC1216. Valid Palindrome III
是LC680的变种，可以greedy检查，然后DFS

Binary Search

对于一个有序数组，其中一个数字出现了一次，其他都出现了两次，求出现一次数字的位置
划分数组使得子数列的和的最大值最小

LC410. Split Array Largest Sum
在答案域上binary search，如果能快速验证

Binary search也可以用来确认一个数组的结尾在哪里
比如一个大小为N的数组，前k个都是1，其余是0，找k
可以用binary search去找最后一个1

binary search的本质不在于找到某一个确定的点，本质在于可以每次排除一半的可能

Complete tree上的binary search，每次寻址logN，所以是O(log^2N)
比如
LC222. Count Complete Tree Nodes

同类型的题还有在complete tree上每一行都是有序的，查找某一个值，也是在一层上binary search

在写binary search的时候，一定保证每次都能缩小范围，比如l = med+1, r= med-1，防止死循环

Union Find

Tarjan Off-line LCA

Tarjan LCA
注意，general的LCA应该是一个map from ElementType to SetType

Bucket

google rain

对于数字范围很小的情况，考虑bucket
LC1057. Campus Bikes
因为distance是0～2000，所以可以考虑用bucket sort代替heap sort

对于N个元素，找前k个，就是O(Nlogk)
但是如果可以落在M个bucket里面，那么就是O(M+N)

Sliding Window Median，加上条件数字都在M范围内，那么也可以用bucket

Other Trick

Zig-Zag Print

Another Zig-Zag Print

Summary of Method